public class VstavkaSort {

	public static void main(String[] args) {

		int[] mas = { 3, 5, 1, 12, 31 };
		for (int i = 0; i < mas.length; i++) {
			System.out.print(mas[i] + ",");
		}
		System.out.println();

		mas = sort(mas);

		for (int i = 0; i < mas.length; i++) {
			System.out.print(mas[i] + ",");
		}

	}

	public static int[] sort(int[] mas) {

		int len = mas.length;

		for (int i = 1; i < len; i++) {
			int plIndex = findPlaceIndex(mas, i);
			mas = insert(mas, i, plIndex);
		}
		return mas;
	}

	public static int findPlaceIndex(int[] mas, int startInd) {

		int index = startInd;
		int val = mas[startInd];
		for (int i = startInd; i >= 0; i--) {
			if (mas[i] <= val) {
				//mas[i]= val ;
				index = i;
				//return index;
			}
			
		}
		return index;

	}

	public static int[] insert(int[] mas, int sourceInd, int destInd) {

		int index = sourceInd;
		int sourceVal = mas[sourceInd];
		for (int i = index - 1; i >= destInd; i--) {
			mas[i + 1] = mas[i];
		}
		mas[destInd] = sourceVal;
		return mas;

	}

}
